/**
  @(#)$Id: AL_QueueCircularSeq.h 73 2013-10-10 12:38:11Z xiaoting $
  @brief   To take advantage of vector space, to overcome the "false overflow" phenomenon is: the vector space imagined as an end to 
  end of the ring, saying such a vector is cyclic vector. Stored in a queue which is called circular queue (Circular Queue).
  
  A queue is a special linear form, so special is that it only allows the front end of the table (front) delete operation, 
  and the rear end of the table (rear) for insertion, and the stack, as the queue is an operating by restricted linear form. Insert 
  operation is called the tail end, the end delete operation called HOL. No element in the queue, it is called an empty queue.
  
  This data structure in the queue, the first element inserted will be the first element to be removed; otherwise the last inserted 
  element will be the last element to be removed, so the queue is also known as "first in first out" (FIFO-first in first out) linear 
  form.

  ////////////////////////////////Sequential storage structure//////////////////////////////////////////
  Using a set of addresses in the computer storage unit sequentially stores continuous linear form of individual data elements, called 
  the linear order of the table storage structure.

  Sequential storage structure is a type of a storage structure, the structure is the logically adjacent nodes stored in the physical 
  location of the adjacent memory cells, the logical relationship between nodes from the storage unit to reflect the adjacency. 
  Storage structure thus obtained is stored in order structure, usually by means of sequential storage structure computer programming 
  language (e.g., c / c) of the array to describe.

  The main advantage of the storage structure in order to save storage space, because the allocation to the data storage unit storing 
  all nodes with data (without regard to c / c language in the array size required for the case), the logical relationship between 
  the nodes does not take additional storage space. In this method, the node can be realized on a random access, that is, each node 
  corresponds to a number, the number can be calculated directly from the node out of the memory address. However, the main 
  disadvantage of sequential storage method is easy to modify the node insert, delete operations, may have to move a series of nodes.
          
  Benefits:
	Random Access table elements. 
  Disadvantages: 
    insert and delete operations need to move elements.

  @Author $Author: xiaoting $
  @Date $Date: 2013-10-10 20:38:11 +0800 (周四, 10 十月 2013) $
  @Revision $Revision: 73 $
  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_QueueCircularSeq.h $
  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_QueueCircularSeq.h 73 2013-10-10 12:38:11Z xiaoting $
 */

#ifndef CXX_AL_QUEUECIRCULARSEQ_H
#define CXX_AL_QUEUECIRCULARSEQ_H

///////////////////////////////////////////////////////////////////////////
//			AL_QueueCircularSeq
///////////////////////////////////////////////////////////////////////////

template<typename T> 
class AL_QueueCircularSeq
{
public:
	static const DWORD QUEUESEQ_DEFAULTSIZE			= 100;
	static const DWORD QUEUESEQ_MAXSIZE				= 0xffffffff;
	/**
	* Construction
	*
	* @param DWORD dwSize (default value: STACKSEQ_DEFAULTSIZE)
	* @return
	* @note
	* @attention
	*/
	AL_QueueCircularSeq(DWORD dwSize = QUEUESEQ_DEFAULTSIZE);

	/**
	* Destruction
	*
	* @param
	* @return
	* @note
	* @attention
	*/
	~AL_QueueCircularSeq();

	/**
	* IsEmpty
	*
	* @param	VOID
	* @return	BOOL
	* @note		Returns true queue is empty
	* @attention
	*/
	BOOL IsEmpty() const;

	/**
	* Front
	*
	* @param	T& tTypeOut <OUT>
	* @return	BOOL
	* @note		Returns a reference to the first element at the front of the queue.
	* @attention
	*/
	BOOL Front(T& tTypeOut) const;

	/**
	* Back
	*
	* @param	T& tTypeOut <OUT>
	* @return	BOOL
	* @note		Returns a reference to the last and most recently added element at the back of the queue.
	* @attention
	*/
	BOOL Back(T& tTypeOut) const;

	/**
	* Pop
	*
	* @param	T& tTypeOut <OUT>
	* @return	BOOL
	* @note		Removes an element from the front of the queue.
	* @attention
	*/
	BOOL Pop(T& tTypeOut);

		
	/**
	* Push
	*
	* @param	VOID
	* @return	DWORD
	* @note		Adds an element to the back of the queue.
	* @attention	
	*/
	VOID Push(const T& tData);

	/**
	* Size
	*
	* @param	VOID
	* @return	DWORD
	* @note		Returns the number of elements in the queue
	* @attention
	*/
	DWORD Size() const;

	/**
	* Clear
	*
	* @param	VOID
	* @return	VOID
	* @note		clear all data
	* @attention
	*/
	VOID Clear();
	
protected:
private:
	/**
	* GetBuffer
	*
	* @param VOID
	* @return VOID
	* @note get the work buffer
	* @attention when the buffer is not enough, it will become to double
	*/
	VOID GetBuffer();
	
	/**
	* IsFull
	*
	* @param VOID
	* @return BOOL
	* @note the buffer is full?
	* @attention
	*/
	BOOL IsFull() const;

	/**
	*Copy Construct
	*
	* @param const AL_QueueCircularSeq<T>& cAL_QueueCircularSeq
	* @return
	*/
	AL_QueueCircularSeq(const AL_QueueCircularSeq<T>& cAL_QueueCircularSeq);

	/**
	*Assignment
	*
	* @param const AL_QueueCircularSeq<T>& cAL_QueueCircularSeq
	* @return AL_QueueCircularSeq<T>&
	*/
	AL_QueueCircularSeq<T>& operator = (const AL_QueueCircularSeq<T>& cAL_QueueCircularSeq);

public:
protected:
private: 
	T*			m_pElements;
	DWORD		m_dwMaxSize;
	DWORD		m_dwSize;

	DWORD		m_dwFront;
	DWORD		m_dwRear;
};


/**
* Construction
*
* @param DWORD dwSize (default value: STACKSEQ_DEFAULTSIZE)
* @return
* @note
* @attention
*/
template<typename T> 
AL_QueueCircularSeq<T>::AL_QueueCircularSeq(DWORD dwSize):
m_pElements(NULL),
m_dwMaxSize(dwSize),
m_dwSize(0x00),
m_dwFront(0x00),
m_dwRear(0x00)
{
	if (0x00 == m_dwMaxSize) {
		//for memory deal
		m_dwMaxSize = 1;
	}
	GetBuffer();
}

/**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
template<typename T> 
AL_QueueCircularSeq<T>::~AL_QueueCircularSeq()
{
	if (NULL != m_pElements) {
		delete[] m_pElements;
		m_pElements = NULL;
	}
}

/**
* IsEmpty
*
* @param	VOID
* @return	BOOL
* @note		Returns true queue is empty
* @attention
*/
template<typename T> BOOL 
AL_QueueCircularSeq<T>::IsEmpty() const
{
	return (0x00 == m_dwSize) ? TRUE:FALSE;
}


/**
* Front
*
* @param	T& tTypeOut <OUT>
* @return	BOOL
* @note		Returns a reference to the first element at the front of the queue.
* @attention
*/
template<typename T> BOOL 
AL_QueueCircularSeq<T>::Front(T& tTypeOut) const
{
	if (TRUE ==IsEmpty()) {
		return FALSE;
	}

	tTypeOut = m_pElements[m_dwFront];
	return TRUE;
}

/**
* Back
*
* @param	T& tTypeOut <OUT>
* @return	BOOL
* @note		Returns a reference to the last and most recently added element at the back of the queue.
* @attention
*/
template<typename T> BOOL 
AL_QueueCircularSeq<T>::Back(T& tTypeOut) const
{
	if (TRUE ==IsEmpty()) {
		return FALSE;
	}

	tTypeOut = m_pElements[m_dwRear];
	return TRUE;
}

/**
* Pop
*
* @param	T& tTypeOut <OUT>
* @return	BOOL
* @note		Removes an element from the front of the queue.
* @attention
*/
template<typename T> BOOL 
AL_QueueCircularSeq<T>::Pop(T& tTypeOut)
{
	if (TRUE ==IsEmpty()) {
		return FALSE;
	}
	tTypeOut = m_pElements[m_dwFront];
	//memset(&m_pElements[m_dwFront], 0x00, sizeof(T));		//can not use memset, as to pointer or virtural pointer of class
	
	m_dwFront = (m_dwFront+1)%m_dwMaxSize;
	
	m_dwSize--;
	return TRUE;
}

	
/**
* Push
*
* @param	VOID
* @return	DWORD
* @note		Adds an element to the back of the queue.
* @attention	
*/
template<typename T> VOID 
AL_QueueCircularSeq<T>::Push(const T& tData)
{
	if (TRUE == IsFull()) {
		// full, need to get more work buffer
		GetBuffer();
	}

	if (0x00 == m_dwFront && TRUE == IsEmpty()) {
		//the first time Push, not need to ++
		m_dwRear = 0x00;
	}
	else {
		m_dwRear = (m_dwRear+1)%m_dwMaxSize;
	}
	m_pElements[m_dwRear] = tData;
	
	m_dwSize++;
}

/**
* Size
*
* @param	VOID
* @return	DWORD
* @note		Returns the number of elements in the queue
* @attention
*/
template<typename T> DWORD 
AL_QueueCircularSeq<T>::Size() const
{
	return m_dwSize;
}

/**
* Clear
*
* @param	VOID
* @return	VOID
* @note		clear all data
* @attention
*/
template<typename T> VOID 
AL_QueueCircularSeq<T>::Clear()
{
	//memset(m_pElements, 0x00, sizeof(T)*Size());		//can not use memset, as to pointer or virtural pointer of class
	m_dwSize = 0x00;
	m_dwFront = 0x00;
	m_dwRear = 0x00;
}


/**
* GetBuffer
*
* @param VOID
* @return VOID
* @note get the work buffer
* @attention when the buffer is not enough, it will become to double
*/
template<typename T> VOID 
AL_QueueCircularSeq<T>::GetBuffer()
{

	if ( (FALSE == IsFull()) && (NULL != m_pElements) ) {
		//we do not need to get more buffer
		return;
	}

	if (NULL == m_pElements) {
		if(0 < m_dwMaxSize){
			//get the new work buffer
			m_pElements = new T[m_dwMaxSize];
			//memset(m_pElements, 0x00, sizeof(T)*m_dwMaxSize);		//can not use memset, as to pointer or virtural pointer of class
		}
		return;
	}

	//we need to get more buffer, store the previous pointer
	T* pLastTpye = NULL;

	// it will become to double
	pLastTpye = m_pElements;
	if (QUEUESEQ_MAXSIZE == m_dwMaxSize) {
		//can not get more buffer, please check the application
		return;
	}
	else if (QUEUESEQ_MAXSIZE/2 < m_dwMaxSize) {
		m_dwMaxSize = QUEUESEQ_MAXSIZE;
	}
	else {
		m_dwMaxSize *= 2;
	}
	if(0 < m_dwMaxSize){
		//get the new work buffer
		m_pElements = new T[m_dwMaxSize];
		//memset(m_pElements, 0x00, sizeof(T)*m_dwMaxSize);		//can not use memset, as to pointer or virtural pointer of class
	}
	//need to copy the last to the current
	for (DWORD dwCpy=0x00; dwCpy<Size(); dwCpy++) {
		m_pElements[dwCpy] = pLastTpye[(m_dwFront+dwCpy)%Size()];
	}

	//memcpy(m_pElements, &pLastTpye[m_dwFront], sizeof(T)*(Size()-m_dwFront));	//can not use memcopy, as to pointer
	//memcpy(m_pElements+(Size()-m_dwFront), &pLastTpye[0], sizeof(T)*m_dwFront);	//can not use memcopy, as to pointer
	
	//m_dwFront move to the front
	m_dwFront = 0x00;
	//m_dwFront move to the rear
	m_dwRear = Size() - 1;

	//free the last work buffer
	delete[] pLastTpye;
	pLastTpye = NULL;
}

/**
* IsFull
*
* @param
* @return BOOL
* @note the buffer is full?
* @attention
*/
template<typename T> BOOL 
AL_QueueCircularSeq<T>::IsFull() const
{
	return (m_dwMaxSize <= Size()) ? TRUE:FALSE;

// 	/*"Sacrifice a unit", ie rear +1 = front (accurately recorded is (rear +1)% m = front, m is the queue capacity) 
// 	when the team is full.*/
// 	if (TRUE == IsEmpty()) {
// 		return FALSE;
// 	}
// 
// 	return ((m_dwRear+1)%m_dwMaxSize == m_dwFront) ? TRUE:FALSE;
}

#endif // CXX_AL_QUEUECIRCULARSEQ_H
/* EOF */
